package com.le.tester.imooc.oldfairy.dynamic;

import org.junit.Test;

import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * createTime：2023/5/31 15:30
 * description：动态规划，最优路径
 */
public class BestPath {

    public List<int[]> bestChoice(int[][] map) {

        //存储路径
        LinkedList<int[]> path = new LinkedList<>();

        int length = map.length;

        //对于动态规划的解法，以后统一叫dp
        int[][][] dp = new int[length + 1][length + 1][3];

        for (int i = 1; i < length + 1; i++) {
            //构建哨兵值
            dp[i][0][0] = -1000;
            dp[0][i][0] = -1000;
        }

        //寻找值，使用坐标点的形式，构造的哨兵，使得从一进行
        for (int y = 1; y < length + 1; y++) {
            for (int x = 1; x < length + 1; x++) {
                int max = dp[y - 1][x - 1][0];
                int px = x - 1;
                int py = y - 1;

                if (dp[y - 1][x][0] > max) {
                    max = dp[y - 1][x][0];
                    px = x;
                }

                if (dp[y][x - 1][0] > max) {
                    max = dp[y][x - 1][0];
                    px = x - 1;
                    py = y;
                }

                dp[y][x][0] = max + map[y - 1][x - 1];

                dp[y][x][1] = px;

                dp[y][x][2] = py;

                System.out.format("fill:dp=%d, px=%d, py=%d\n", dp[y][x][0], px, py);
            }
        }

        System.out.println("--- dp table ---");

        for (int i = 0; i < length + 1; i++) {
            for (int j = 0; j < length + 1; j++) {
                System.out.format("%7d ", dp[i][j][0]);
            }
            System.out.println();
        }

        int x = length;
        int y = length;

        path.addFirst(new int[]{x - 1, y - 1});
        while (true) {
            int px = dp[y][x][1];

            int py = dp[y][x][2];

            x = px;

            y = py;

            if (x == 0 && y == 0) {
                break;
            }

            path.addFirst(new int[]{x - 1, y - 1});
        }
        return path;
    }

    @Test
    public void test() {

        int[][] map = new int[][]{
                {5, 4, 2, 2},
                {8, 0, 5, 17},
                {4, 1, 2, 0},
                {1, 4, 6, 3}
        };

        List<int[]> path = bestChoice(map);
        System.out.println(path.stream().map(x -> String.format("(%d, %d)", x[0], x[1])).collect(Collectors.toList()));

        System.out.print("best path is:");
        for (int[] p : path) {
            System.out.print(map[p[1]][p[0]]);
            System.out.print("->");
        }
        System.out.println();
    }
}
